﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol739
{
    public int[] DailyTemperatures2(int[] temperatures)//暴力法，n2，很容易超时
    {

        int len= temperatures.Length;
        int[] higher=new int[len];
        for (int i=0; i < len; i++)
        {
            for(int j=i; j < len; j++)
            {
                if(temperatures[j] > temperatures[i])
                {
                    higher[i] = j-i;
                    break;
                }
            }

        }

        return higher;


    }
    //单调栈法
    public int[] DailyTemperatures(int[] temperatures)//温度低的都入栈，遇到温度高的出站，出站次数就是
    {

        int len = temperatures.Length;
        int[] higher = new int[len];
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < len; i++)
        {
            while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()])
            {
                int preIndex = stack.Pop();
                higher[preIndex] = i - preIndex;
            }
            stack.Push(i);

        }
        return higher;  


        }
}
class Program739
{

    static void Main739()
    {
        int[] temp = { 73, 74, 75, 71, 69, 72, 76, 73 };


        Sol739 sol= new Sol739();
        int[] res= sol.DailyTemperatures(temp);
        for (int i = 0; i < res.Length; i++) {

            Console.WriteLine(res[i]);

        }
        

    }
}
